



class Solution:

    def orangeRotting(self, grid: list[list[int]]) -> int:

        M = len(grid)
        N = len(grid[0])

        # 存储腐烂橘子的队列
        queue = []

        count = 0 

        for r in range(M):

            for c in range(N):

                if grid[r][c] == 1:
                    count += 1

                elif grid[r][c] == 2:
                    queue.append((r, c))

        round = 0

        while count > 0 and len(queue) > 0:
            round += 1
            n = len(queue)
            # 每一个轮次
            for _ in range(n):
                r, c = queue.pop(0)
                # 不能超出边界范围
                if r - 1 >= 0 and grid[r-1][c] == 1:
                    grid[r-1][c] = 2
                    count -= 1
                    queue.append((r-1, c))

                if r + 1 < M and grid[r+1][c] == 1:
                    grid[r+1][c] = 2
                    count -= 1
                    queue.append((r+1, c))

                if c - 1 >= 0 and grid[r][c-1] == 1:
                    grid[r][c-1] = 2
                    count -= 1
                    queue.append((r, c-1))

                if c + 1 < N and grid[r][c+1] == 1:

                    grid[r][c+1] = 2
                    count -= 1
                    queue.append((r, c+1))


        if count > 0:
            return -1
        
        return round
            

if __name__ == "__main__":

    a = [[2,1,1],[1,1,0],[0,1,1]]

    sol = Solution()
    res = sol.orangeRotting(a)

    print(res)
